package array.sliding_window;
/*
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

        异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。



        示例 1:

        输入: s = "cbaebabacd", p = "abc"
        输出: [0,6]
        解释:
        起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
        起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
        示例 2:

        输入: s = "abab", p = "ab"
        输出: [0,1,2]
        解释:
        起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
        起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
        起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
*/

import java.util.ArrayList;
import java.util.List;

public class lc438 {
    public static void main(String[] args) {
       String s = "cbaebabacd";
       String p = "abc";
        List<Integer> anagrams = findAnagrams(s, p);
        System.out.println();

    }
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> result=new ArrayList<>();
        int p_length = p.length();  //字串
        int s_length = s.length();//母串
        char[] p_chars = p.toCharArray();
        char[] s_chars = s.toCharArray();
        int[] hashmap=new int[26];
        for (int i = 0; i <p_length ; i++) {
            hashmap[p_chars[i]-'a']++;
        }
        int c=0;

        int right=p_length-1;
        int slow=0;
        while (right<s.length()){
            int[] hashmap_back=new int[26];//备份hashmap
            for (int i = 0; i <26 ; i++) {
                hashmap_back[i]=hashmap[i];
            }
            for (int j = slow; j <slow+p_length ; j++) {
                hashmap_back[s_chars[j]-'a']--;
            }
            for (c = 0; c <26 ; c++) {
                if (hashmap_back[c]!=0){
                    break;
                }
            }
            if(c==26){
                result.add(slow);
            }
           slow++;
           right++;

        }
        return result;

    }
}
